package learn.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "a", "A");
        HeroNode node2 = new HeroNode(2, "b", "B");
        HeroNode node3 = new HeroNode(3, "c", "C");
        HeroNode node4 = new HeroNode(4, "d", "D");
        SingleLinkedList linkedList = new SingleLinkedList();

//        testAdd(node1, node2, node3, node4, linkedList);
//        testAddByOrder(node1, node2, node3, node4, linkedList);
//        testUpdate(node1, node2, node3, node4, linkedList);
//        testDelete(node1, node2, node3, node4, linkedList);
//        testCount(node1, node2, node3, node4, linkedList);

//        testFindLastNode(node1, node2, node3, node4, linkedList);
//        testReversedList(node1, node2, node3, node4, linkedList);
//        testReversedPrint(node1, node2, node3, node4, linkedList);
        testMerge(node1, node2, node3, node4);
    }

    private static void testMerge(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4) {
        SingleLinkedList linkedList1 = new SingleLinkedList();
        linkedList1.addByOrder(node2);
        linkedList1.addByOrder(node4);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addByOrder(node1);
        linkedList2.addByOrder(node2);
        SingleLinkedList merge = SingleLinkedList.merge2(linkedList1.head, linkedList2.head);
        merge.list();
    }

    private static void testReversedPrint(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node4);
        System.out.println("原链表");
        linkedList.list();
        System.out.println("倒序链表");
        SingleLinkedList.reversedPrint(linkedList.head);

        System.out.println("原链表没有发生变化");
        linkedList.list();
    }

    private static void testReversedList(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node4);
        SingleLinkedList.reversedList(linkedList.head);
        linkedList.list();
    }

    private static void testFindLastNode(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node4);
        System.out.println("获取倒数第K个： " + linkedList.findLastNode(linkedList.head, 2));
    }

    private static void testCount(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        System.out.println("有效节点格式： " + linkedList.getLength(linkedList.head));
    }

    private static void testUpdate(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        System.out.println("修改前");
        linkedList.list();
        HeroNode node = new HeroNode(3, "ccc", "CCC");
        linkedList.update(node);
        System.out.println("修改后");
        linkedList.list();
    }

    private static void testAddByOrder(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node3);
        linkedList.list();
    }

    private static void testAdd(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.add(node1);
        linkedList.add(node4);
        linkedList.add(node2);
        linkedList.add(node3);
        linkedList.list();
    }

    private static void testDelete(HeroNode node1, HeroNode node2, HeroNode node3, HeroNode node4, SingleLinkedList linkedList) {
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);
        System.out.println("删除前");
        linkedList.list();
        linkedList.delete(4);
        System.out.println("删除后");
        linkedList.list();
    }
}

class SingleLinkedList {
    //初始化head
    public final HeroNode head = new HeroNode(0, "", "");

    /**
     * 1 找到当前链表最后的节点
     * 2 将最后节点的next赋值为入参
     *
     * @param node
     */
    public void add(HeroNode node) {
        //因为head不能动，因此需要一个赋值变量
        HeroNode temp = head;
        //遍历链表取到最后
        while (temp.next != null) {
            temp = temp.next;
        }
        //退出循环时，temp为链表的末尾
        temp.next = node;
    }

    /**
     * 找到需要插入的节点的前一个节点
     *
     * @param node
     */
    public void addByOrder(HeroNode node) {
        //因为head不能动，因此需要一个赋值变量
        //temp位于添加位置的前一个节点
        HeroNode temp = head;
        //添加的编号是否存在
        boolean loop = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > node.no) {
                //就在temp.next的前面插入数据
                break;
            } else if (temp.next.no == node.no) {
                loop = true;
                break;
            }
            temp = temp.next;
        }
        if (loop) {
            System.out.println("插入的数据已存在 no= " + temp.no);
        } else {
            //将node插入到temp与temp.next之间
            //将temp.next挂载到node的尾部
            node.next = temp.next;
            //将node挂载到temp的尾部
            temp.next = node;
        }
    }

    public void update(HeroNode node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //辅助节点
        HeroNode temp = head.next;

        boolean flag = false;

        while (true) {
            if (temp == null) {
                //链表已经遍历完成
                break;
            }
            if (temp.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        System.out.println("原节点为：" + temp.toString());
        temp.name = node.name;
        temp.nickname = node.nickname;
        System.out.println("修改后的节点为：" + temp.toString());
    }

    public void delete(int no) {
        /**
         * 1 找到需要删除的节点的前一个节点temp
         * 2 temp.next = temp.next.next
         */
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //辅助节点
        HeroNode temp = head;

        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("未找到需要删除的节点");
        }
    }

    /**
     * 统计节点个数，去掉头节点
     *
     * @return int
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) {
            return 0;
        }
        HeroNode temp = head;
        int count = 0;
        while (true) {
            if (temp.next == null) {
                break;
            }
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 倒数第K个就是正数 length-K
     *
     * @param head
     * @param index
     * @return HeroNode
     */
    public static HeroNode findLastNode(HeroNode head, int index) {
        if (head.next == null) {
            return null;
        }
        int length = getLength(head);
        if (index <= 0) {
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0; i < length - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public static void reversedList(HeroNode head) {
        if (head.next == null || head.next.next == null) return;
        HeroNode cur = head.next;
        HeroNode next = null;//当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", "");
        while (cur != null) {
            next = cur.next;//取出当前节点的下一个节点
            cur.next = reverseHead.next;
            reverseHead.next = cur;//将cur链接到新链表上
            cur = next;//后移一位
        }
        head.next = reverseHead.next;
    }

    public static void reversedPrint(HeroNode head) {
        if (head.next == null || head.next.next == null) return;
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 将输入的两个链表合并，并输出合并好的新链表
     *
     * @param head1
     * @param head2
     * @return SingleLinkedList
     */
    public static SingleLinkedList merge2(HeroNode head1, HeroNode head2) {
        if (head1.next == null && head2.next == null) return null;
        SingleLinkedList result = new SingleLinkedList();
        result.head.next = head1.next;//将链表1复制到目标链表上
        HeroNode temp = head2.next;
        while (true) {
            if (temp == null) {
                break;
            }
            HeroNode next = temp.next;
            temp.next = null;
            result.addByOrder(temp);
            temp = next;
        }
        return result;
    }

    /**
     * 将输入的两个链表合并，并输出合并好的新链表
     *
     * @param head1
     * @param head2
     * @return SingleLinkedList
     */
    public static SingleLinkedList merge(HeroNode head1, HeroNode head2) {
        if (head1.next == null && head2.next == null) return null;
        SingleLinkedList result = new SingleLinkedList();
        HeroNode resultHead = result.head;
        resultHead.next = head1.next;//将链表1复制到目标链表上
        HeroNode temp = head2.next;
        while (true) {
            if (temp == null) {
                break;
            }
            HeroNode resultTemp = resultHead;
            while (true) {
                if (resultTemp.next == null) {
                    break;
                }
                if (resultTemp.next.no > temp.no) {
                    break;
                }
                resultTemp = resultTemp.next;
            }
            HeroNode next = temp.next;
            temp.next = resultTemp.next;
            resultTemp.next = temp;
            temp = next;
        }

        return result;
    }

    /**
     * 显示链表
     */
    public void list() {
        if (head.next == null) {
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            System.out.println(temp.toString());
            if (temp.next == null) {
                break;
            }
            //后移temp
            temp = temp.next;
        }
    }
}

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}